package com.xinwei.leetcode.数组;

// https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

// 虽然这题做出来了 但是思路很差劲，，应该写个独特的二分查找：
//先找>=target的第一个
//再找>target的第一个
public class _34_在排序数组中查找元素的第一个和最后一个位置 {
    public static int[] searchRange(int[] nums, int target) {

        // 先找到相等的值，然后往左右两边走
        int left = 0;
        int right = nums.length - 1;
        int[] result = new int[]{-1, -1};
        if (nums == null || nums.length == 0) return result;
        if (nums.length == 1) {
            if (nums[0] != target) {
                return result;
            }else {
                return new int[]{0,0};
            }
        }
        int index = search(nums, 0, nums.length, target);
        if (index == -1) {
            return result;
        }
        left = index;
        right = index;
        while (left >= 0) {
            if (nums[left] != nums[index]) {
                left++;
                break;
            }
            if (left != 0) {
                left--;
            }else {
                break;
            }
        }
        while (right < nums.length) {
            if (nums[right] != nums[index]) {
                right--;
                break;
            }
            if (right != nums.length - 1){
                right++;
            }else {
                break;
            }
        }
        result[0] = left;
        result[1] = right;
        return result;
    }

    private static int search(int[] nums, int left, int right, int target) {
        int mid = (left + right) >> 1;
        if (target == nums[mid]) return mid;
        if (right - left <= 1) return -1;
        if (target > nums[mid]) {
            return search(nums, mid, right, target);
        }else {
            return search(nums, left, mid, target);
        }
    }
}
